<?php

class MatrixApp {
	
	private $nodeValues;
	private $matrix;
	private $statistics;
	private $transitionMatrix;
	private $pageRanks;
	
	public function __construct() {
		$this->nodeValues = array();
		$this->matrix = array();
		$this->transitionMatrix = array();
		$this->pageRanks = array();
	}
	
	public function init($fileName) {
		$this->readData($fileName);
		
		$this->generateMatrix();
		$this->assignAssociations($fileName);
	}
	
public function calculatePageRankIterative($repetitions = 10, $dampingFactor = 0.8) {
	$n = count($this->nodeValues);
	foreach ($this->nodeValues as $u) {
		$this->pageRanks[$u] = (1 / $n);
		
	}
	
	for ($i = 0; $i < $repetitions; $i++) {
		$this->calculatePageRank($dampingFactor);
	}
	$sum = 0;
	foreach ($this->pageRanks as $u => $value) {
		$sum += $value;
	}
	
	echo 'Sum: ' . $sum . '<br>';
	return $this->pageRanks;
}
	
protected function calculatePageRank($dampingFactor = 0.8) {
	$n = count($this->nodeValues);
	$stakes = array();
	foreach ($this->nodeValues as $u) {
		$this->stakes[$u] = 0;
	}
	
	
	foreach ($this->pageRanks as $u => $value) {
		$referers = $this->getReferers($u);
		$pageRank = (1 - $dampingFactor) / $n;
		$sum = 0;
		
		foreach ($referers as $referer) {
			$neighbors = $this->searchNeighbors($referer);
			$sum += ((1 / $n) / count($neighbors));
		}
		
		$pageRank += ($dampingFactor * $sum);
		
		$this->pageRanks[$u] = $pageRank;
		/**
		 * When calculating PageRank, pages with no outbound links are assumed to
		 * link out to all other pages in the collection. Their PageRank scores
		 * are therefore divided evenly among all other pages.
		 **/
		$outboundLinks = $this->searchNeighbors($u);
		if (count($outboundLinks) == 0) {
			foreach ($this->stakes as $name => $value) {
				if ($name != $u) {
					$this->stakes[$name] += (($dampingFactor / $n) / ($n - 1));
				}
			} 
		}
	}
	
	foreach ($this->pageRanks as $name => $value) {
		$this->pageRanks[$name] += $this->stakes[$name];
	}
	

	return $this->pageRanks;
}
	
	private function getReferers($u) {
		$referers = array();
		foreach ($this->matrix as $i => $row) {
			if ($this->matrix[$i][$u] == 1) {
				$referers[$i] = $i;
			}
		}
		
		return $referers;
	}
	
	public function stationaryDistribution($repetitions = 1000, $steps = 10, $vertex = '1') {
		$original = $this->generateTransitionMatrix();
		
		for ($i = 0; $i < 100; $i++) {
			if ($i == 0) {
				$transitionMatrix = $original;
			}
			$transitionMatrix = $this->multiplyTransitionMatrix($transitionMatrix, $original);
		}
		
		$this->writeInFile($transitionMatrix);
		
		return $transitionMatrix;
	}
	
	public function writeInFile($transitionMatrix) {
		$file = fopen('stationaryDistribution.txt', 'w+');

		foreach ($transitionMatrix as $row) {
			$values = implode("\t", $row);
			fwrite($file, $values . PHP_EOL);
		}
		
		fclose($file);
	}
	
	public function generateTransitionMatrix() {
		foreach ($this->nodeValues as $i) {
			$neighbors = $this->searchNeighbors($i);
			$probability = 1 / count($neighbors);			// probability = 1 / degree
			
			foreach ($this->nodeValues as $j) {

				if ($this->matrix[$i][$j] == 1 && $i != $j) {
					$this->transitionMatrix[$i][$j] = $probability;
				} else {
					$this->transitionMatrix[$i][$j] = 0;
				}
			}
		}
		
		
		return $this->transitionMatrix;
	}
	
	public function pagelink($repetitions = 1000, $steps = 10, $vertex = '1') {
		for ($i = 0; $i < $repetitions; $i++) {
			$lastVertex = $this->randomWalk($steps, $vertex);
			if (isset($this->statistics[$lastVertex])) {
				$this->statistics[$lastVertex] += 1;
			} else {
				$this->statistics[$lastVertex] = 1;
			}
		}
		
		ksort($this->statistics);		// Sort by values
		return $this->statistics;
	}
	
	public function readData($fileName) {
		$file = fopen($fileName, 'r');

		$header = fgets($file);
		
		while (!feof($file)) {
			$line = fgets($file);
						
			list($from, $to) = preg_split('/\s+/', $line);
			
			if (!isset($this->nodeValues[$from])) {
				$this->nodeValues[$from] = $from;
			}
			
			if (!isset($this->nodeValues[$to])) {
				$this->nodeValues[$to] = $to;
			}
		}
		
		asort($this->nodeValues);
		
		fclose($file);
	}
	
	public function generateMatrix() {
		foreach($this->nodeValues as $x) {
			foreach ($this->nodeValues as $y) {
				$this->matrix[$x][$y] = 0;
			}
		}
		
		return $this->matrix;
	}
	
	public function assignAssociations($fileName) {
		$file = fopen($fileName, 'r');

		$header = fgets($file);
		
		while (!feof($file)) {
			$line = fgets($file);
						
			list($from, $to) = preg_split('/\s+/', $line);
			$this->matrix[$from][$to] = 1;
		}
		
		fclose($file);
		
		return $this->matrix;
	}
	
	public function getMatrix() {
		
		return $this->matrix;
	}
	
	public function multiplyTransitionMatrix($first, $second) {
		$result = array();
		foreach ($this->nodeValues as $i) {
			foreach ($this->nodeValues as $j) {
				foreach ($this->nodeValues as $k) {
					if (!isset($result[$i])) {
						$result[$i] = array();
					}
					if (!isset($result[$i][$j])) {
						$result[$i][$j] = 0;
					}
					
					$result[$i][$j] += ($first[$i][$k] * $second[$k][$j]);
				}
			}
		}
		
		return $result;
	}
	public function multiply($first, $second) {
		$result = array();
		foreach ($this->nodeValues as $i) {
			foreach ($this->nodeValues as $j) {
				foreach ($this->nodeValues as $k) {
					if (!isset($result[$i])) {
						$result[$i] = array();
					}
					if (!isset($result[$i][$j])) {
						$result[$i][$j] = 0;
					}
					
					$result[$i][$j] |= ($first[$i][$j] || ($first[$i][$k] && $second[$k][$j]));
				}
			}
		}
		
		return $result;
	}
	
	public function warhsall($first, $second) {
		$result = array();
		foreach ($this->nodeValues as $k) {
			foreach ($this->nodeValues as $i) {
				foreach ($this->nodeValues as $j) {
					if (!isset($result[$i])) {
						$result[$i] = array();
					}
					if (!isset($result[$i][$j])) {
						$result[$i][$j] = array();
					}
					
					$result[$i][$j] |= ($first[$i][$j] || ($first[$i][$k] && $second[$k][$j]));
				}
			}
		}
		
		return $result;
	}
	
	public function randomWalk($steps = 10, $vertex = '1') {
		while ($steps > 0) {
			$neighbors = $this->searchNeighbors($vertex);
			shuffle($neighbors);
			$vertex = array_pop($neighbors);
			
			$steps--;
		}
		
		return $vertex;
	}
	
	protected function searchNeighbors($vertex) {
		$neighbors = array();
		$row = $this->matrix[$vertex];
		foreach ($this->nodeValues as $k) {
			if ($row[$k] == 1) {
				$neighbors[] = $k;
			}
		}
		
		return $neighbors;
	}
}